1. Field of the Invention
The present invention relates to adder circuits for modern central processing units (CPUS) of digital computers and, more particularly, to carry selected adders.
2. Prior Art
In principle, binary sums are computed by computing the sum of two input bits with equal significance and the corresponding carry in. The result is one bit of the sum of the same significance, and the carry out, which is carry in for the computation of the next more significant bit. Sequential propagation of carries (ripple carry adder) with state of the art adders is only appropriate for operands that are only a few bits wide.
State of the art addition in hardware uses a recursive divide and conquer strategy to speed up carry propagation. The most widely used fast binary adder algorithm is the carry-look-ahead adder. The basic principle is a divide and conquer strategy to handle carry propagation.
The operands are split into parts, e.g. lower significant and higher significant half. The 2n bit adder 10n correspondingly is divided into a more significant component 19n and a less significant component 18n as shown in FIG. 1a, which compute the sum of the more significant and less significant operand parts. This split is continued until the operands are one bit wide as shown in FIG. 1b. There a half adder performs the initial operation. A half adder adds two bits, producing one bit sum so and one bit carry co.
FIGS. 1a and 1b show the handling of the carry propagation: a carry is propagated through a basic element, if the half adder's sum is 1. A carry is propagated through a combination of two parts, if both parts propagate carry, thus cp for both elements is 1. The carry propagation thus is handled by an AND tree of AND gates 16n.
The real carry propagation is computed backward then. Each part outputs carry co, if both carry in ci and carry propagate cp is true, or the higher significant subpart outputs carry from OR gate 17n as seen in FIG. 1a. The so bits of the sum are computed with an exclusive or of the sum output, e.g. with XOR gate 12 from the sum output of the 1 bit adder 14 with the corresponding carry in, ci. The gate delay per subdivision (by two) thus is three elementary gates (two input AND/OR or NAND/NOR gates), which are often combined into one large gate. In FIGS. 1a and 1b the AND gate is indicated symbolically with &, the OR gate, with .vertline. and the XOR gate, with .LAMBDA..
Carry-look-ahead logic is further improved combining a higher number of parts (e.g. four instead of two) in one step and using larger gates (with more than two inputs) in turn. Carry select logic is used to speed up carry propagation, leading to a critical path of e.g. four large gates for a 64 bit adder.
Carry select adders compute both the sum with and without carry (thus a+b and a+b+1 for inputs a and b) for a number of subpartitions. Carry in of each subpartition is used to select the correct sum of the next subpartition (towards higher significance) using a n bit wide multiplexer. The subpartitions usually are computed using ripple carry addition. Carry propagation can be improved using carry look ahead logic.